package th.retrofit.lib;

/**
 * https://leetcode-cn.com/problems/gas-station/
 * 在一条环路上有N个加油站，其中第i个加油站有汽油gas[i]升。
 *
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，开始时油箱为空。
 *
 * 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
 *
 * 说明:
 *
 * 如果题目有解，该答案即为唯一答案。
 * 输入数组均为非空数组，且长度相同。
 * 输入数组中的元素均为非负数。
 *
 */
public class Solution134 {

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int gSize = gas.length;
        int totalRemain = 0;
        int subRemain = 0;
        int startPos = -1;
        for (int i = 0; i < gSize; i++) {
            int remain = gas[i] - cost[i];
            subRemain += remain;
            if (subRemain < 0) {
                startPos = i + 1;
                subRemain = 0;
            }
            totalRemain += remain;
        }
        if (totalRemain < 0) {
            startPos = -1;
        }
        return startPos;
    }

    public static void main(String[] args) {
        System.out.println(new Solution134().canCompleteCircuit(new int[]{6,1,4,3,5}, new int[]{3,8,2,4,2}));
    }

}
